/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/restore-ip-addresses
   @Language: C++
   @Datetime: 19-07-09 17:03
   */

class Solution {
	bool isvalid(const string &s){
		if(s[0]=='0' && s.length()>1) return false;
		return stoi(s)<256;
	}
	void backtrack(string &s, int pos, int dots, string &t, vector<string> &vs){
		if(dots==4){
			if(pos==s.length()){
				vs.push_back(t);
				vs.back().pop_back();   // trim last dot
			}
			return;
		}
		for(int i=1; i<4 && pos+i<=s.length(); ++i){
			string str=s.substr(pos,i);
			if(!isvalid(str)) continue;
			str=t+str+".";
			backtrack(s,pos+i,dots+1,str,vs);
		}
	}
public:
	vector<string> restoreIpAddresses(string &s) {
		string t;
		vector<string> vs;
		backtrack(s,0,0,t,vs);
		return vs;
	}
};
